package code301_400.code90_100;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
 *
 * 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
 * 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
 * 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
 * 给你整数 n ，返回 arr 最后剩下的数字。
 *
 * 输入：n = 9
 * 输出：6
 * 解释：
 * arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 * arr = [2, 4, 6, 8]
 * arr = [2, 6]
 * arr = [6]
 *
 * 输入：n = 1
 * 输出：1
 */
public class _390lastRemaining {

    /**
     * 第一种最笨的方法，直接构建10^9次方列表 进行模拟操作！
     * 难点 ： 模拟难以实现，且在实际运算过程中超时。
     * @param n
     * @return
     */
    public int lastRemaining0(int n) {
        ArrayDeque<Integer> list = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        // 0表示从左到右，1表示从右到左
        int flag = 0;
        while (list.size()!=1){
            if(flag%2==0){
                list.removeFirst();
            }else {
                list.removeLast();
            }
        }
        return 0;
    }

    /**
     * 题解思路 ： 等差数列模拟
     * 依照题意每次将整数列表进行间隔删除，因此每次删除后剩余的整数列表都是等差数列。
     * 假设第k次删除后的等差数列的首元素为a1K，末尾元素为anK，公差为stepK，元素数目为cntK，则在k+次删除后的等差数列满足。
     * stepK+1 = stepK*2；
     * cntK+1 = 【cntK/2】;
     * 初始时k=0，表示尚未删除任何元素。
     *
     * 如果k是偶数，则从左向右删除，反之从右向左删除
     * 当等差数列只剩一个元素，即cntK = 1时，返回首元素a1K即可。
     * @param n
     * @return
     */
    public int lastRemaining(int n){
        int a1 = 1;
        int k = 0,cnt = n,step = 1;
        while (cnt>1){
            if(k%2==0){
                a1 = a1 + step;
            }else {
                a1 = (cnt%2==0)?a1:a1+step;
            }
            k++;
            cnt = cnt>>1;
            step = step<<1;
        }
        return a1;
    }

    /**
     * 来自题解评论
     * 真实模拟过程，这个模拟法也挺精妙的！
     * @param n
     * @return
     */
    public int lastRemaining1(int n) {
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<n;i++){list.add(i+1);}
        int d=0;
        while(true){
            d++;
            if(d%2==1){
                for(int i=0;i<list.size();i++){
                    if(list.size()==1){return list.get(0);}
                    list.remove(i);
                }
            }
            else{
                for(int i=list.size()-1;i>=0;i-=2){
                    if(list.size()==1){return list.get(0);}
                    list.remove(i);
                }
            }
        }
    }

    /**
     * 来自题解评论
     * 其实不用实际真的移除，记录一下每次剩下的最大最小值喝本轮移除的等差数列就好了
     * @param n
     * @return
     */
    public int lastRemaining2(int n) {
        int num=n;//记录剩下的数字数目
        int l=1;//记录最小值
        int r=n;//记录最大值
        int d=0;//记录循环次数
        int lift=1;//记录最值的增大或减小的幅度
        while(num>2){
            d++;
            if(num%2==1||num%2==0&&d%2==1){l+=lift;}
            if(num%2==1||num%2==0&&d%2==0){r-=lift;}
            num/=2;
            lift*=2;
        }
        return num==2&&d%2==0?r:l;
    }

}
